package com.vincent.exam.linkedList;

/**
 * 利用快慢指针方法判断链表是否存在环，并记录两指针相遇位置。
 * 题目描述：对于一个给定的链表，返回环的入口节点，如果没有环，返回null
 * 快慢指针方法:将两指针分别放在链表头（X）和相遇位置（Z），并改为相同速度推进，则两指针在环开始位置相遇（Y），如图所示。
 *
 * 证明过程：X，Y，Z分别为链表起始位置，环开始位置和两指针相遇位置，由快指针速度的慢指针速度的2倍。
 *
 *
 * 快指针与慢指针均从X出发，在Z相遇。此时，慢指针行使距离为a+b，快指针为a+b+n(b+c）。
 * 所以2*(a+b)=a+b+n*(b+c),推出
 * a=(n-1)*b+n*c=(n-1)(b+c)+c;
 * 得到，将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。
 */
public class FindListNode {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!= null && fast.next!= null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                // 有环,都改成慢速
                ListNode slow2 = head;
                while(slow2!=slow){
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}
